
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
  <meta charset="utf-8">
  <title>Memory Consistency和Cache Coherence - Yebangyu's Blog</title>
  <meta name="author" content="Yebangyu">

  
  <meta name="description" content="Cache Coherence Memory Consistency 缓存一致性 内存模型 Sequential Consistency">
  <meta name="keywords" content="Cache Coherence Memory Consistency 缓存一致性 内存模型 Sequential Consistency">

  <!-- http://t.co/dKP3o1e -->
  <meta name="HandheldFriendly" content="True">
  <meta name="MobileOptimized" content="320">
  <meta name="viewport" content="width=device-width, initial-scale=1">

  
  <link rel="canonical" href="http://www.yebangyu.org/blog/2016/01/09/memoryconsistencyandcachecoherence/">
  <link href="/favicon.png" rel="icon">
  <link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
  <link href="/atom.xml" rel="alternate" title="Yebangyu's Blog" type="application/atom+xml">
  <script src="/javascripts/modernizr-2.0.js"></script>
  <script src="//ajax.lug.ustc.edu.cn/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
  <script>!window.jQuery && document.write(unescape('%3Cscript src="/javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
  <script src="/javascripts/octopress.js" type="text/javascript"></script>
  <!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>

  

</head>

<body   >
  <header role="banner"><hgroup>
  <h1><a href="/">Yebangyu's Blog</a></h1>
  
    <h2>Fond of Concurrency Programming and Machine Learning</h2>
  
</hgroup>

</header>
  <nav role="navigation"><ul class="subscription" data-subscription="rss">
  <li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
  
</ul>
  
<form action="https://www.google.com/search" method="get">
  <fieldset role="search">
    <input type="hidden" name="sitesearch" value="www.yebangyu.org">
    <input class="search" type="text" name="q" results="0" placeholder="Search"/>
  </fieldset>
</form>
  
<ul class="main-navigation">
  <li><a href="/">Blog</a></li>
  <li><a href="/blog/archives">Archives</a></li>
  <li><a href="/about">About Me</a></li>
</ul>

</nav>
  <div id="main">
    <div id="content">
      <div>
<article class="hentry" role="article">
  
  <header>
    
      <h1 class="entry-title">Memory Consistency和Cache Coherence</h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-01-09T22:52:52+08:00'><span class='date'><span class='date-month'>Jan</span> <span class='date-day'>9</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:52 pm</span></time>
        
      </p>
    
  </header>


<div class="entry-content"><h2 id="memory-consistency">Memory Consistency</h2>

<p><strong>Memory Consistency</strong>(<strong>MC</strong>)，有时候又叫做<strong>Memory Consistency Model</strong>或者<strong>Memory Model</strong>。为了理解为什么需要引入这种东西，我们首先看以下程序：</p>

<!--more-->

<pre><code>初始：x=0 y=0

Thread1：

S1：x=1

L1：r1=y

Thread2：

S2：y=2

L2：r2=x
</code></pre>

<p>其中，<strong>S1、S2、L1、L2</strong>是语句代号（<strong>BTW</strong>，<strong>S</strong>表示<strong>Store</strong>，<strong>L</strong>表示<strong>Load</strong>）；<strong>r1</strong>和<strong>r2</strong>是两个寄存器。<strong>x</strong>和<strong>y</strong>是两个不同的内存变量。</p>

<p>两个线程执行完之后，<strong>r1</strong>和<strong>r2</strong>可能是什么值？</p>

<p>注意到线程是并发、交替执行的，下面是可能的执行顺序和相应结果：</p>

<p><strong>S1 L1 S2 L2</strong> 那么<strong>r1=0 r2=2</strong></p>

<p><strong>S1 S2 L1 L2</strong> 那么<strong>r1=2 r2=1</strong></p>

<p><strong>S2 L2 S1 L1</strong> 那么<strong>r1=2 r2=0</strong></p>

<p>这些都是意料之内、情理之中的。但是在<strong>x86</strong>体系结构下，很可能得到<strong>r1=0 r2=0</strong>这样的结果。是不是大吃一惊？</p>

<p>如果没有<strong>Memory Consistency</strong>，那么程序员对于自己编写的多线程程序会输出什么将一无所知：天知道会输出什么。</p>

<p>因此，<strong>Memory Consistency</strong>就是程序员（编程语言）、编译器、CPU间的一种协议。这个协议保证了程序访问内存时可能得到什么值，会得到什么值。</p>

<h2 id="sequential-consistency">Sequential Consistency</h2>

<p>在<strong>Sequential Consistency</strong>这种<strong>Memory Model</strong>下，刚才讨论的那个程序不可能输出<strong>r1=0 r2=0</strong>这种结果。怎么说？这就牵涉到一个问题：什么是<strong>Sequential Consistency</strong>（<strong>SC</strong>）。</p>

<p>根据<strong>Leslie Lamport</strong>在<strong>1979</strong>年<strong>9</strong>月发表的论文《<strong>How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs</strong>》里提出的<strong>SC</strong>的定义：</p>

<p>the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.</p>

<p>根据这个定义，在<strong>SC</strong>模型下，任何<strong>execution</strong>的执行顺序（我们称为<strong>Memory Order</strong>）必须<strong>respect</strong>每个线程的<strong>Program Order</strong>。什么是<strong>Program Order</strong>？对于以上程序，在<strong>Thread1</strong>中，<strong>S1</strong>先于<strong>L1</strong>（不妨记为<strong>S1&lt;L1</strong>）；在<strong>Thread2</strong>中，<strong>S2</strong>先于<strong>L2</strong>（记为<strong>S2&lt;L2</strong>）。这就是<strong>Program Order</strong>。</p>

<p>请时刻注意，<strong>Program Order</strong>只针对某个线程内的语句而言，不涉及到跨线程。比如<strong>Thread1</strong>中的<strong>S1</strong>和<strong>Thread2</strong>中的<strong>L2</strong>，就无所谓什么<strong>Program Order</strong>了。</p>

<p>好了，现在知道为什么在<strong>SC</strong>下，有些结果可能出现，有些不可能了。</p>

<p><strong>S1 L1 S2 L2 r1=0 r2=2</strong> 没问题，没有违背<strong>S1&lt;L1 S2&lt;L2</strong></p>

<p><strong>S1 S2 L1 L2 r1=1 r2=2</strong> 没问题，没有违背<strong>S1&lt;L1 S2&lt;L2</strong></p>

<p><strong>S2 L2 S1 L1 r1=2 r2=0</strong> 没问题，没有违背<strong>S1&lt;L1 S2&lt;L2</strong></p>

<p>而对于<strong>r1=0 r2=0</strong>，在<strong>SC</strong>下，我们找不到一个能<strong>respect Program Order</strong>的<strong>Memory Order</strong>。因为<strong>r1=0</strong>，说明<strong>L1&lt;S2</strong>，<strong>r2=0</strong>说明<strong>L2&lt;S1</strong>；而<strong>S1&lt;L1，S2&lt;L2</strong>，不难看出这里形成了一个环。</p>

<h2 id="cache-coherence">Cache Coherence</h2>

<p>还是先搬出这张图吧:</p>

<p><img src="http://7xnljs.com1.z0.glb.clouddn.com/cpuand%20cache.png" alt="memorycache" /></p>

<p>(图片来源于<strong>Paul</strong>大叔的《<strong>Is Parallel Programming Hard</strong>》这本书第三章)</p>

<p>多个<strong>CPU cores</strong>，每个<strong>core</strong>上有自己的<strong>Cache</strong>。我们知道，<strong>Cache</strong>是部分内存的映射和缓存，或者说，副本。这就带来一个问题：副本一致性。内存只有一个，每个<strong>cpu cores</strong>却有自己的内存副本，如何保证大家看到的内容是一样的、一致的、正确的呢？这就是<strong>Cache Coherence(CC)</strong>要解决的问题。</p>

<h2 id="cache-coherence--vs-memory-consistency">Cache Coherence  VS Memory Consistency</h2>

<p>从以上分析，我们不难看出，<strong>CC</strong>和<strong>MC</strong>涉及的是两个不同层面的东西，解决的是不同的问题，不可混淆。<strong>CC</strong>解决的是副本一致性问题；<strong>MC</strong>保证的是多线程程序访问内存时可以（可能）读到什么值。</p>

<p>两者有联系吗？有。实现<strong>Memory Consistency</strong>时可能会使用到<strong>Cache Coherence</strong>。细节下次我们接着聊。</p>

<h2 id="section">附录</h2>

<p>1，在并行编程中，我们常常有一个问题，或者需求：比如说上面的那个程序，如何保证线程<strong>2</strong>读到的<strong>x</strong>是线程<strong>1</strong>更新（<strong>x=1</strong>）后的<strong>x</strong>的值呢？</p>

<p>如果不加任何同步设施，仅仅考虑上面的程序，那么答案是：无法保证。因为线程的推进速度不同，哪条指令先被执行也一无所知。这个程序重跑几次，也可能输出不同的结果出来。</p>

<p>也就是说，<strong>Memory Model</strong>保证的是，例如，当线程<strong>2</strong>看到<strong>x</strong>等于<strong>1</strong>的时候，线程<strong>1</strong>是否已经执行了<strong>L1</strong>。也就是说，<strong>Memory Model</strong>确保当一件事情发生时，有其他什么事情<strong>has happened</strong>。在<strong>SC</strong>中，当<strong>L1</strong>发生时，说明或者说暗示着，<strong>S1</strong>已经发生了。</p>

<p>2，为什么<strong>x86</strong>下可能得出<strong>r1=0 r2=0</strong>的结果？</p>

<p>因为<strong>S1</strong>是写一个内存变量而<strong>L1</strong>是读取另一个内存变量（两个变量，或者说两个内存地址），这种情况下的写读可能被<strong>CPU</strong>乱序：先执行<strong>L1</strong>，再执行<strong>S1</strong>。（为了性能，所谓的延后写）</p>

<h2 id="section-1">致谢</h2>

<p>本文发出后，微博网友@linyvxiang 指出了其中的一个笔误，非常感谢。</p>
</div>


  <footer>
    <p class="meta">
      
  

<span class="byline author vcard">Posted by <span class="fn">Yebangyu</span></span>

      




<time class='entry-date' datetime='2016-01-09T22:52:52+08:00'><span class='date'><span class='date-month'>Jan</span> <span class='date-day'>9</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:52 pm</span></time>
      

<span class="categories">
  
    <a class='category' href='/blog/categories/bing-xing-bian-cheng/'>并行编程</a>
  
</span>


    </p>
    
      <div class="sharing">
  
  
  
</div>

    
    <p class="meta">
      
        <a class="basic-alignment left" href="/blog/2016/01/07/timingcprograminlinux/" title="Previous Post: Linux下C++程序计时方法">&laquo; Linux下C++程序计时方法</a>
      
      
        <a class="basic-alignment right" href="/blog/2016/01/17/concurrenyandparallism/" title="Next Post: Concurrent and Parallel">Concurrent and Parallel &raquo;</a>
      
    </p>
  </footer>
</article>


</div>

<aside class="sidebar">
  
    <section>
  <h1>Recent Posts</h1>
  <ul id="recent_posts">
    
      <li class="post">
        <a href="/blog/2017/03/11/2017/">2017技术成长之路</a>
      </li>
    
      <li class="post">
        <a href="/blog/2017/02/17/virtualfunctionandvariadicparametertemplate/">虚函数和变长参数模板的妙用</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/25/singleton/">Singleton与多线程</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/04/introductiontohazardpointer/">Lock Free中的Hazard Pointer(下)</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/03/gccandperfopt/">性能优化的那些传说和迷思</a>
      </li>
    
  </ul>
</section>
<section>
  <h1>Friends' Link</h1>
  <ul>
    <li>
	  <li><a href="http://www.chongh.wiki/">Diting0x</a></li>
	  <li><a href="http://www.xiaolili.net/">wangli</a></li>
	  <li><a href="http://www.skykewei.top">dukewei</a></li>
	  <li><a href="http://irwenqiang.github.io">chenwenqiang</a></li>
      <li><a href="http://www.armsword.com">duruofei</a></li>
    </li>
  </ul>
</section><section>
  <h1>Yebangyu</h1>
  <p>福建人。热爱历史、K歌、NBA</p>
  <p>帝都码农</p>
  <p>历史学家，专治秦汉史</p>
</section>
<section>
 <h1>Categories</h1>
 <ul id="categories">
  <li class='category'><a href='/blog/categories/c-plus-plus/'>c++ (11)</a></li>
<li class='category'><a href='/blog/categories/soupen/'>soupen (4)</a></li>
<li class='category'><a href='/blog/categories/web/'>web (1)</a></li>
<li class='category'><a href='/blog/categories/qi-ta/'>其他 (5)</a></li>
<li class='category'><a href='/blog/categories/li-shi/'>历史 (2)</a></li>
<li class='category'><a href='/blog/categories/bing-xing-bian-cheng/'>并行编程 (20)</a></li>
<li class='category'><a href='/blog/categories/xing-neng-you-hua/'>性能优化 (2)</a></li>
<li class='category'><a href='/blog/categories/suan-fa/'>算法 (4)</a></li>
<li class='category'><a href='/blog/categories/bian-yi-lian-jie/'>编译链接 (2)</a></li>

 </ul>
</section>




  
</aside>


    </div>
  </div>
  <footer role="contentinfo"><!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>
<p>
  Copyright &copy; 2017 - Yebangyu -
  <span class="credit">Powered by <a href="http://octopress.org">Octopress</a></span>
</p>
<script type="text/javascript">var cnzz_protocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1257548193'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s11.cnzz.com/z_stat.php%3Fid%3D1257548193' type='text/javascript'%3E%3C/script%3E"));</script>

</footer>
  











</body>
</html>
